package leetcode每日一题.leetcode20212;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。
 *      窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口
 *      移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q003_滑动窗口中位数 {

    // 暴力法   时间复杂度为O(n * (k+klogk))   空间复杂度为O(k * (n-k+1))
    // 超出时间限制  并不推荐这种暴力的解法
    public double[] medianSlidingWindow1(int[] nums, int k) {
        int len = nums.length;
        double[] res = new double[len - k + 1];
        for(int i = 0; i + k <= len; i++) {
            double[] temp = new double[k];
            for(int j = 0; j < k; j++) {
                temp[j] = nums[j+i];
            }
            Arrays.sort(temp);
            if(k % 2 == 0) {
                res[i] = (temp[k/2-1] + temp[k/2]) / 2;
            } else {
                res[i] = temp[k/2];
            }
        }
        return res;
    }

    // 暴力法2 居然没有超时  整体思路一样，但是代码编写上简化了
    public double[] medianSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        int cnt = n - k + 1;
        double[] ans = new double[cnt];
        int[] tmp = new int[k];
        for (int left = 0, right = left + k - 1; right < n; left++, right++) {
            for (int j = left; j <= right; j++) {
                tmp[j - left] = nums[j];
            }
            Arrays.sort(tmp);
            ans[left] = (tmp[k / 2] / 2.0) + (tmp[(k - 1) / 2] / 2.0);
        }
        return ans;
    }
}
